package stu.day25_day32.day31;

import java.util.*;

public class hw2 {




     public List<List<String>> aList = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        int[][] attack = new int[n][n];
        char[][] queen = new char[n][n];

        for (int[] ints : attack) {
            Arrays.fill(ints,0);
        }
        for (char[] chars : queen) {
            Arrays.fill(chars,'.');
        }

        backtrack(0,n,attack,queen);
        return aList;


    }

    public void backtrack(int num,int n,int[][] attack,char[][] queen){
        if(num==n){
            List<String> list = new ArrayList<>();
            for (char[] chars : queen) {
                list.add(String.copyValueOf(chars));
            }
            aList.add(list);
            return;
        }

        for (int i=0;i<n;i++){
            if(attack[num][i]==0){

                queen[num][i] = 'Q';

                int[][] tep = new int[n][n];
                for (int p=0;p<n;p++) {
                    for (int q=0;q<n;q++){
                        tep[p][q] = attack[p][q];
                    }
                }

                att(num,i,attack);

                backtrack(num+1,n,attack,queen);

                attack = tep;
                queen[num][i] = '.';

            }


        }





    }

    public void att(int num,int i,int[][] attack){
        int[] d1={1,1,-1,-1,1,-1,0,0};
        int[] d2={1,-1,-1,1,0,0,1,-1};

        for(int k=0;k<8;k++){
            for(int j=0;j<attack.length;j++){
                int x = num + d1[k]*j;
                int y = i + d2[k]*j;
                if(x>=0 && x<attack.length && y>=0 && y<attack.length){
                    attack[x][y] = 1;
                }
            }
        }

    }




}
